class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        def isPalindrome(s):
            l = 0
            r = len(s) - 1
            while l <= r:
                if s[l] != s[r]:
                    return False
                l = l + 1
                r = r - 1
            return True

        def backtrace(s, index, path, ans):
            if index == len(s):
                ans.append(path[:])
                return
            
            for i in range(index, len(s)):
                sub = s[index:i+1]
                if isPalindrome(sub):
                    path.append(sub)
                    backtrace(s, i+1, path, ans)
                    path.pop()
        ans = []
        backtrace(s, 0, [], ans)
        return ans
